package com.ryujung.greedy;
/*
 * @lc app=leetcode.cn id=455 lang=java
 *
 * [455] 分发饼干
 */

import java.util.Arrays;

// @lc code=start
class Solution445 {

    /**
     * 思路：
     * 首先将饼干从小到大排序，孩子的需求数也从小到大排序，
     * 然后遍历饼干，
     * 如果当前饼干可以满足当前孩子，则结果加1，当前孩子指向下一个
     * 如果当前饼干不满足当前孩子，饼干向后遍历，孩子不动
     * 直到饼干遍历完
     *
     * 注意：这里的childNum和res其实可以省略其中一个，
     * 因为其变化是完全同步的，分开只是为了看起来便于理解
     */
    public int findContentChildren2(int[] g, int[] s) {
        Arrays.sort(s);
        Arrays.sort(g);
        int res = 0;
        int childNum = 0;
        // 遍历饼干
        for (int i = 0; i < s.length; i++) {
            if (childNum < g.length && s[i] >= g[childNum]) {
                res++;
                childNum++;
            }
        }
        return res;
    }


    public static int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int sIndex = 0, result = 0;
        for (int i = 0; i < g.length && sIndex < s.length; i++, sIndex++) {
            while (sIndex < s.length && g[i] > s[sIndex]) {
                sIndex++;
            }
            if (sIndex >= s.length) {
                break;
            }
            result++;

        }
        return result;
    }

    public static void main(String[] args) {
        int[] g = {1, 2, 3}, s = {1, 1};
        System.out.println(findContentChildren(g, s));
    }

}
// @lc code=end
